package com.kevin.Code.DP;

import scala.Int;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname WordBreak
 * @Description Leetcode 139. 单词拆分 动态规划 中等难度 背包问题
 * @Date 2021/10/9 21:20
 * @Version 1.0
 */
public class WordBreak {

    /**
     * 完全背包问题
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {

        int len = s.length();

        //用hashset数组存储字符
        HashSet<String> hashSet = new HashSet<>(wordDict);


        //定义dp数组，dp[i]表示0.。。。i-1个字符是否可以拆分成题目符合要求的字符串
        //要符合要求比较dp[0...j-1] dp[j...i-1]
        //dp[j]已经求出来 只需要判断dp
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int i = 1; i <= len; i++) {


            for (int j = 0; j < i; j++) {

                if (dp[j] && hashSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }

            }
        }

        return dp[len];

    }


    /**
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak1(String s, List<String> wordDict) {

        int len = s.length();

        //用hashset数组存储字符
        HashSet<String> hashSet = new HashSet<>(wordDict);
        int maxLen = Integer.MIN_VALUE;
        for (String s1 : wordDict) {
            maxLen = Math.max(s1.length(), maxLen);
        }

        //定义dp数组，dp[i]表示0.。。。i-1个字符是否可以拆分成题目符合要求的字符串
        //要符合要求比较dp[0...j-1] dp[j...i-1]
        //dp[j]已经求出来 只需要判断dp
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int i = 1; i <= len; i++) {


            for (int j = 0; j < i; j++) {

                //剪枝
                if (i - j > maxLen) {
                    continue;
                }

                if (dp[j] && hashSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }

            }
        }

        return dp[len];

    }


    public static void main(String[] args) {

        WordBreak wordBreak = new WordBreak();
//        String[] str = new String[]{"leet", "code"};

        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");

        boolean b = wordBreak.wordBreak("leetcode", list);
        System.out.println(b);
    }
}
